package com.skh.linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: skh
 * @Date: 2019/6/13 14:55
 * @Description: 160. 相交链表
 */
public class GetIntersectionNode {
    /*
    编写一个程序，找到两个单链表相交的起始节点。

    如下面的两个链表：

    在节点 c1 开始相交。

    示例 1：

    输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
    输出：Reference of the node with value = 8
    输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
     

    示例 2：

    输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
    输出：Reference of the node with value = 2
    输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
     

    示例 3：

    输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
    输出：null
    输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
    解释：这两个链表不相交，因此返回 null。
     */


    /**
     * 双指针法
     * <p>
     * 创建两个指针 pApA 和 pBpB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
     * 当 pA到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点。
     * 若在某一时刻 pA 和 pB 相遇，则 pA/pB 为相交结点。
     * 想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。
     * 由于 B.length (=4) < A.length (=6)，pB比 pA 少经过 2个结点，会先到达尾部。将 pB 重定向到 A 的头结点，pA 重定向到 B 的头结点后，pB 要比 pA 多走 2 个结点。因此，它们会同时到达交点。
     * 如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。
     * <p>
     * 可以理解成两个人速度一致， 走过的路程一致。
     * 那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话，那么这段路上俩人肯定是肩并肩手牵手的.
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) { //如果最后都不相交,最后都会达到尾部都是Null,就会跳出循环
            if (pA == null) {
                pA = headB;
            } else {
                pA = pA.next;
            }
            if (pB == null) {
                pB = headA;
            } else {
                pB = pB.next;
            }

        }

        return pA;
    }

    /**
     * 针对A和B链表，我们首先使用Set集合存储A中的每一个指针域，
     * 并在存储完毕后开始遍历B链表，看B中的指针是否存在于set集合中，
     * 如果存在，立刻返回该指针，如果遍历完毕依然不包含，我们只能说A和B没有共同交集指针，返回Null，代码也很简洁
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        Set<ListNode> set = new HashSet<>();
        while (pA != null) {
            set.add(pA);
            pA = pA.next;
        }

        while (pB != null) {
            if (set.contains(pB)) {
                return pB;
            }
            pB = pB.next;
        }


        return null;

    }

    /**
     * 暴力法
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;


        while (pA != null) {
            while(pB!=null){
                if(pA==pB){
                    return pA;
                }
                pB = pB.next;
            }
            pA=pA.next;
            pB = headB;
        }
        return null;
    }


    /*
    思路：1.计算两个链表的长度
         2.计算长度差,让长的链表先走长度差,得到等长的两个链表
         3.再遍历两个链表,逐一比较.如果有相同的值,说明相交了.
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) {
            return null;
        }

        ListNode a = headA;
        ListNode b = headB;

        int aLength = 0;
        while (a != null) {
            aLength++;
            a = a.next;
        }

        int bLength = 0;
        while (b != null) {
            bLength++;
            b = b.next;
        }

        if (aLength > bLength) {
            int l = aLength - bLength;
            while (l > 0) {
                headA = headA.next;
                l--;
            }
        } else {
            int l = bLength - aLength;
            while (l > 0) {
                headB = headB.next;
                l--;
            }
        }

        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }

            headA = headA.next;
            headB = headB.next;

        }


        return null;
    }

    public static void main(String[] args) {

        ListNode headA = ListNode.createListNode("4,1,8,4,5");

        ListNode headB = new ListNode(5);
        ListNode nodeB2 = new ListNode(0);
        ListNode nodeB3 = new ListNode(1);
        ListNode nodeB4 = new ListNode(8);
        ListNode nodeB5 = new ListNode(4);
        ListNode nodeB6 = new ListNode(5);
        headB.next = nodeB2;
        nodeB2.next = nodeB3;
        nodeB3.next = nodeB4;
        nodeB4.next = nodeB5;
        nodeB5.next = nodeB6;


        //while (headA != null) {
        //    System.out.println(headA);
        //    headA = headA.next;
        //}

        //while (headB != null) {
        //    System.out.println(headB);
        //    headB = headB.next;
        //}

        GetIntersectionNode getIntersectionNode = new GetIntersectionNode();
        ListNode intersectionNode = getIntersectionNode.getIntersectionNode(headA, headB);
        ListNode.printListNode(intersectionNode);

    }

}
